package com.bit;

/**
 * @className: com.bit.BitMap
 * @description: 位图实现
 * @author: tong.li
 * @createTime: 2022/7/27 19:30
 * @copyright: Tongcheng-Elong Holdings Limited
 */
public class BitMap {

    /**
     * 1个long表示64个位，极大的压缩空间
     */
    private long[] bits;


    /**
     * 构造并初始化位图数组大小
     *  初始化数组大小：以最大值来确定位图数组的大小
     *  max = 8, size = 1； max = 67, size = 2
     *  注意：加64原因是，申请数组的大小不能为0
     * @param max
     */
    public BitMap(int max) {
        bits = new long[(max + 64) >> 6];
    }

    /**
     * 给位图添加一个数：
     *   1. 找到这个数存放在数组的第那个元素，假设这个元素在数组的i位置上 --> 除64
     *   2. 第i个元素找到后，这个数应该存放在该元素上哪个位上，记为j --> 求余64
     *   3. 将64位的1向左移动j位，即000010000这种形式，那么在|上原数并放回数组原位置，则可以把j设置为1
     * @param value
     */
    public void add(int value) {
        // 索引从0开始, value >> 6 ==> value / 64
        // value % 64 ==> value & 63 63是6个全1,高位舍弃，只取后6位，那么就是求余
        // 一定要注意这里必须写成64位的1L，写1就成为32位了
        bits[value >> 6] |= (1L << (value & 63));
    }

    /**
     * 在位图中删除一个数
     *   1. 找到这个数存放在数组的第那个元素，假设这个元素在数组的i位置上 --> 除64
     *   2. 第i个元素找到后，这个数应该存放在该元素上哪个位上，记为j --> 求余64
     *   3. 将64位的1向左移动j位后取反，即1110111这种形式，那么在&上原数并放回数组原位置，则可以把j设置为0
     * @param value
     */
    public void delete(int value) {
        // 索引从0开始, value >> 6 ==> value / 64
        // value % 64 ==> value & 63 63是6个全1,高位舍弃，只取后6位，那么就是求余
        // 一定要注意这里必须写成64位的1L，写1就成为32位了
        bits[value >> 6] &= ~(1L << (value & 63));
    }

    /**
     * 判断一个数在不在位图中
     * @param value
     *   1. 找到这个数存放在数组的第那个元素，假设这个元素在数组的i位置上 --> 除64
     *   2. 第i个元素找到后，这个数应该存放在该元素上哪个位上，记为j --> 求余64
     *   3. 将64位的1向左移动j位后，即000010000这种形式，那么在&上原数，若结果是0则不包含该数，反之存在该数
     * @return
     */
    public boolean contains(int value) {
        // 索引从0开始, value >> 6 ==> value / 64
        // value % 64 ==> value & 63 63是6个全1,高位舍弃，只取后6位，那么就是求余
        // 一定要注意这里必须写成64位的1L，写1就成为32位了
        return (bits[value >> 6] & (1L << (value & 63))) != 0;
    }


}
